In the field of robotics, much interest has been generated over the years in methods of collision avoidance between a robot and obstacles in its environment. Methods of collision avoidance have at their core, a method of collision detection. In general, to prevent a collision, the intersection of a set of moveable elements with a set of obstacles must be determined before the collision actually occurs. After it has been determined that a collision state is imminent, action can be taken to redirect the robot to avoid the collision.
Two broad categories of collision detection methods are: those methods that encode the occupancy of obstacles in a spatial index, and those that do not. Methods relating to the latter category, while satisfactory for on-line path planning, tend to be too slow to be effective for real-time collision avoidance. Typically a collision is detected by analytically calculating the distance between a set of geometric primitives describing a moveable element, and a set of geometric primitives describing obstacles. Determination of the collision status of the moveable element therefore requires the intersection calculation to be performed a number of times, equal to the product of the number of geometric primitives describing the moveable element and the number of geometric primitives describing the obstacles.
Lozano-Perez in a paper entitled "Spatial Planning: A Configuration Space Approach," IEEE Transactions on Computers, vol. C-32, no. Feb. 2, 1983 teaches a method of the second category heretofore mentioned. Lozano-Perez models both the moveable elements and the obstacles as polyhedra, and analytically calculates the intersections of planes.
Khatib, O., in a paper entitled "Real-Time Obstacle Avoidance for Manipulators and Mobile Robots," published in The International Journal of Robotics Research, vol. 5 no. 1, Spring 1986, models moveable elements as a set of points and line segments and presents the analytical distance formulae for a number of geometric primitives, including a parallelepiped, a cylinder, and a cone. Dodds, G., in a paper entitled "Robotic Collision Control", IEEE Colloquium on controllers for Robotic Applications--Concepts and Implementations, Digest no. 127, 1989, pp. 2/1-2/4 models moveable elements as spheres, and the obstacles as polyhedra; it has been suggested by others to model the moveable elements and obstacles as polyhedra, cylinders or spheres.
One technique that improves the processing speed of collision detection is to encode the occupancy of the obstacles in a spatial index. An example of this is the use of voxels. Voxels are discrete volume elements in the form of cubes. In some known schemes, all the voxels that are occupied by an obstacle are assigned a predetermined value, for example zero, while all other voxels are given another value. To determine whether a certain point in space is occupied by an obstacle, it is sufficient to perform a simple table lookup, locating the corresponding voxel and checking its value.
Advantageously, this method obviates the need to perform an analytic calculation of the distance between the geometric primitives describing the moveable elements and the geometric primitives describing the obstacles. Rather, the geometric primitives describing the moveable elements need only be compared to the values of the voxels that are quick to identify.
Duffy et al. in a paper entitled "Real-Time Collision Avoidance System for Multiple Robots Operating in a Shared Workspace", IEEE Proceedings, Vol. 36, Pt. E, No. Nov. 6, 1989, pp. 478-484 describe a system wherein both the moveable element and the obstacles are represented as sets of voxels, and a specialized digital hardware system was constructed to determined the overlap of these sets as the element moves thorough space.
Although the prior art methods for collision avoidance and detection appear to perform their intended function, some of these methods are too slow for real-time applications.
Therefore, it is an object of the invention to provide a method for collision detection that can determine a collision state in a timely manner.
Furthermore, it is an object of the invention to provide a method of collision detection wherein the speed of detection is independent of the number of obstacles in the environment.
In accordance with an aspect of the invention, in a device having one or more moveable elements residing within a finite space, a method of detecting a collision state between an object within the finite space and a model of the one or more moveable elements, comprising the steps of: (a) determining relative strengths of a set of discrete points throughout the space, the relative strength of any point being a measure of the distance from that point to the object; (b) storing values representative of the relative strengths in a memory; (c) determining values of relative strengths of a set of reference points which approximate a volume occupied by the model of the one or more moveable elements, the relative strength of each point being a measure of the distance around that point that is occupied by the model of the one or more moveable elements; (e) storing values representive of the relative strengths of the set of reference points in a memory and identifying a corresponding discrete point for each reference point; and, (f) comparing the stored values representative of the relative strengths of the reference points with the stored values representative of the relative strengths of the corresponding discrete points in the space, a collision state being detected when the ratio of any of the compared values representative of the relative strengths of the reference points and the values representative of the relative strengths of the corresponding discrete points in the space is greater than 1.
In accordance with another aspect of the invention in a device having a plurality of relatively moveable elements, there is provided a method of detecting a collision state between an object and a model of one of the moveable elements before a collision occurs, comprising the steps of: determining the value of the strength of each of a plurality of voxels within a finite space, the strength of any voxel being an indicator of the distance from that voxel to the object; identifying the voxel address at the center of one or more spheres which approximates a volume occupied by the model of the moveable element; and, comparing the values of the strengths of the voxels at the centers of the one or more spheres with a number of adjacent voxels that correspond to the respective radii of the one or more spheres, a collision state being detected when a compared value of the strength of the voxel at the center of a sphere is less than the value of the radii of that sphere.